package com.cjm.algorithm.tanxin;

import com.sun.org.apache.xpath.internal.operations.Bool;

import java.util.HashMap;
import java.util.Map;

public class Ti647 {
    public static void main(String[] args) {
        Ti647 ti647 = new Ti647();
        System.err.println(ti647.countSubstrings("abc"));
        System.err.println(ti647.countSubstrings("abba"));
    }


    Map<String, Boolean> is = new HashMap<>();
    public int countSubstrings(String s) {
        is.clear();
        int[] dp = new int[s.length()];
        dp[0] = 1;
        for (int i = 1; i < s.length(); i++) {
            dp[i] = getCurrentNum(i, s) + dp[i-1];
        }
        return dp[s.length() - 1];
    }


    private int getCurrentNum(int end, String s) {
        int x = 0;
        for (int i = 0; i <= end; i++) {
            String substring = s.substring(i, end+1);
            if (is.get(substring) != null && is.get(substring)) {
                x++;
                continue;
            }
            if (is.get(substring) != null && !is.get(substring)) {
                continue;
            }
            boolean huiWenChuan = isHuiWenChuan(substring);
            is.put(substring, huiWenChuan);
            if (huiWenChuan) {
                x++;
            }
        }
        return x;
    }

    private boolean isHuiWenChuan(String s) {
        if (s.length() <= 1) {
            return true;
        }

        for (int i = 0; i < s.length(); i++) {
            int head = i;
            int end = s.length() - (i + 1);
            if (head > end ) break;
            if (s.charAt(head) != s.charAt(end)) {
                return false;
            }
        }
        return true;
    }
}
